package 左哥算法.ch02二分;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

public class ch01_2_随机快排 {
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    static Random random = new Random();

    public void sort(int[] nums, int l, int r) {
        if (l >= r) return;
        int v = nums[l + random.nextInt(r - l + 1)];
        int m = l;
        int vi = l;
        for (int i = l; i <= r; i++) {
            if (nums[i] <= v) {
                int temp = nums[i];
                nums[i] = nums[m];
                nums[m] = temp;
                if (v == nums[m]) vi = m;
                m++;
            }
        }
        int temp = nums[vi];
        nums[vi] = nums[m - 1];
        nums[m - 1] = temp;
        sort(nums, l, m - 2);
        sort(nums, m, r);
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 5, 4, 2};
        sortArray(arr);
        System.out.println(Arrays.toString(arr));
    }
}
